383C - Propagating tree - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
vector<int> g[maxn];
int sz[maxn], pi[maxn];
bool block[maxn];
int a[maxn];
int n;

int centroid(int v, int p, int n) {
  sz[v] = 1;
  int mx=0, cen=0;
  for (auto u : g[v]) if (u!=p && !block[u]) {
      cen ^= centroid(u, v, n);
      sz[v] += sz[u], mx = max(mx, sz[u]);
  }
  mx = max(mx, n-sz[v]);
  if (2*mx <= n) pi[cen=v]=p;
  return cen;
}

void decompose(int x, int p=-1, int m=n) {
  int cen = centroid(x, -1, m);
  if (~pi[cen]) sz[pi[cen]]=m-sz[cen];
  pi[cen]=p; block[cen]=1;
  for (auto v : g[cen]) if (!block[v])
      decompose(v, cen, sz[v]);
}

int T;
int lo[maxn], hi[maxn];
bool h[maxn];
void dfs(int x, int p=-1, int he=0) {
  lo[x] = T++; h[x] = he;
  for (auto v : g[x]) if (v^p)
      dfs(v, x, he^1);
  hi[x] = T++;
}

int ft[maxn];
void update(int x, int add) {
  bool he = h[x];
  for (int ll=lo[x], rr=hi[x];~x; x=pi[x])
     ft[x] += (ll <= lo[x] && hi[x] <= rr) * (2*(he ^ h[x])-1)* add;
}

int query(int x) {
  bool he = h[x];
  int ans=0;
  for (int ll=lo[x], rr=hi[x]; ~x; x=pi[x])
      ans += (lo[x] <= ll && rr <= hi[x]) * (2*(he^h[x])-1)*ft[x];
  return ans;
}

int main() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i=1; i<=n; ++i) {
      scanf("%d", a+i);
  }
  for (int i=0; i<n-1; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(1, -1);
  decompose(1);
  for (int i=0; i<m; ++i) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int x, val;
      scanf("%d%d", &x, &val);
      update(x, val);
    } else {
      int x;
      scanf("%d", &x);
      printf("%d\n", a[x] + query(x));
    }
  }
  return 0;
}